// 定义边的结构体
class Edge {
	from: number;
	to: number;
	weight: number;
	constructor(from: number, to: number, weight: number) {
		this.from = from;
		this.to = to;
		this.weight = weight;
	}
}

class Graph {
	private n: number; // 节点数量
	private edges: Edge[]; // 边的集合
	private graph: number[][]; // 邻接矩阵表示的图
	private dis: number[]; // 从起点到每个节点的最短距离
	private visited: boolean[]; // 记录每个节点是否已访问过

	constructor(n: number, edges: number[][]) {
		this.n = n;
		this.edges = edges.map(([from, to, weight]) => new Edge(from, to, weight));
		// 初始化邻接矩阵
		this.graph = new Array(n).fill(undefined).map(() => new Array(n).fill(Number.MAX_VALUE));
		for (let i = 0; i < n; i++) {
			this.graph[i][i] = 0;
		}

		// 建立邻接矩阵
		for (const { from, to, weight } of this.edges) {
			this.graph[from][to] = weight;
		}

		// 初始化起点到每个节点的最短距离
		this.dis = new Array(n).fill(Number.MAX_VALUE);
		this.visited = new Array(n).fill(false);
	}

	// 小根堆**弹出堆顶元素**
	private heapPop(heap: number[][]): number[] {
		const res = heap[0];
		heap[0] = heap[heap.length - 1];
		heap.pop();
		/**
		 * 小根堆的**下沉**操作
		 *
		 * @param heap
		 * @param idx
		 */
		function siftDown(heap: number[][], idx: number): void {
			const leftChild = idx * 2 + 1;
			const rightChild = idx * 2 + 2;
			let minIdx = idx;
			if (leftChild < heap.length && rightChild < heap.length) {
				minIdx = heap[leftChild][0] < heap[rightChild][0] ? leftChild : rightChild;
			} else if (leftChild < heap.length) {
				minIdx = leftChild;
			} else if (rightChild < heap.length) {
				minIdx = rightChild;
			}
			if (minIdx !== idx && heap[minIdx][0] < heap[idx][0]) {
				[heap[idx], heap[minIdx]] = [heap[minIdx], heap[idx]];
				siftDown(heap, minIdx);
			}
		}
		siftDown(heap, 0);
		return res;
	}

	// 小根堆**插入元素**
	private heapPush(heap: number[][], x: number[]): void {
		heap.push(x);
		/**
		 * 小根堆的**上浮**操作
		 *
		 * @param heap
		 * @param idx
		 */
		function siftUp(heap: number[][], idx: number): void {
			const parent = Math.floor((idx - 1) / 2);
			if (idx > 0 && heap[idx][0] < heap[parent][0]) {
				[heap[idx], heap[parent]] = [heap[parent], heap[idx]];
				siftUp(heap, parent);
			}
		}
		siftUp(heap, heap.length - 1);
	}

	/**
	 * Dijkstra 算法计算单源最短路径
	 *
	 * 堆优化的 Dijkstra 算法时间复杂度为 O(ElogE)，但是因为这里是邻接矩阵存图，所以 E = O(N^2)，因此总时间复杂度为 O(N^2logN)。
	 *
	 * @param start
	 */
	private dijkstra(start: number): void {
		this.dis[start] = 0;
		const heap: number[][] = [[0, start]]; // 用小根堆存放 <起点到某个节点的最短距离，节点编号> 这个二元组
		while (heap.length) {
			const [d, u] = this.heapPop(heap); // 取出堆顶元素，即当前距离起点最近的节点
			if (this.visited[u]) continue; // 如果该节点已访问过，继续循环下一个节点
			this.visited[u] = true; // 标记该节点已访问过
			for (let i = 0; i < this.n; i++) {
				// 遍历与当前节点相连的点
				if (this.graph[u][i] < Number.MAX_VALUE) {
					// 如果两点之间有连线，则尝试松弛操作
					if (this.dis[i] > this.dis[u] + this.graph[u][i]) {
						// 如果经过当前节点到达该点的距离更短，就更新 dis 数组
						this.dis[i] = this.dis[u] + this.graph[u][i];
						this.heapPush(heap, [this.dis[i], i]); // 将该点推入堆中，用于检查是否可以通过其他路径到达更小距离的节点
					}
				}
			}
		}
	}

	addEdge(edge: number[]): void {
		this.edges.push(new Edge(edge[0], edge[1], edge[2]));
		this.graph[edge[0]][edge[1]] = edge[2];
		this.dis = new Array(this.n).fill(Number.MAX_VALUE);
		this.visited = new Array(this.n).fill(false);
	}

	shortestPath(node1: number, node2: number): number {
		this.dis = new Array(this.n).fill(Number.MAX_VALUE);
		this.visited = new Array(this.n).fill(false);

		this.dijkstra(node1);
		if (this.dis[node2] === Number.MAX_VALUE) {
			// 如果无法到达该节点，返回 -1
			return -1;
		}
		return this.dis[node2];
	}
}

/**
 * Your Graph object will be instantiated and called as such:
 * var obj = new Graph(n, edges)
 * obj.addEdge(edge)
 * var param_2 = obj.shortestPath(node1,node2)
 */
